#pragma once
#include <map>
#include <limits>
#include <vector>
#include <list>
#include <stack>

using std::map;
using std::list;
using std::pair;
using std::vector;
using std::make_pair;

enum EColour{WHITE,GRAY,BLACK};

template <typename Name>
class BiGraph {
  public:
    class Vertex;
    class Edge;

    template <typename T, typename U>
    class Iterator{
      public:
        Iterator(T It):ptr(It) {};
        Iterator& operator++(){ptr++; return *this;}
        Iterator& operator--(){ptr--; return *this;}
        Iterator operator++(int){Iterator temp; temp.ptr=ptr; ptr++; return temp;}
        Iterator operator--(int){Iterator temp; temp.ptr=ptr; ptr--; return temp;}
        bool operator==(const Iterator& It) const {return (ptr==It.ptr);}
        bool operator!=(const Iterator& It) const {return (ptr!=It.ptr);}
        U& operator*(){ return *(ptr->second); }
        U* operator->(){ return ptr->second; }
        Iterator& operator=(const Iterator& It) {ptr=It.ptr; return *this;}

      private:
        T  ptr;
    };

    typedef typename map<Name,Vertex*>::iterator map_NV_It;
    typedef typename map<Vertex*, Edge*>::iterator map_VE_It;
    typedef Iterator< map_NV_It, Vertex > Vertex_Iterator;
    typedef Iterator< map_VE_It, Edge > In_Edge_Iterator;
    typedef Iterator< map_VE_It, Edge > Out_Edge_Iterator;

    typedef std::pair<Vertex_Iterator, Vertex_Iterator> Vertices_Range;

    class Edge{
        friend class BiGraph;
      public:
        Edge(Vertex* start, Vertex* end, double w): f(0), c(w), start_vertex(start), end_vertex(end) {}
        pair<Name, Name> get_name() const { return make_pair(start_vertex->get_name(), end_vertex->get_name()); }
        pair<Vertex*,Vertex*> get_vertices() const { return make_pair(start_vertex, end_vertex); }
        bool closed;
        double f;
        double c;

      private:
        Vertex* start_vertex;
        Vertex* end_vertex;
    };

    class Vertex{
        friend class BiGraph;
      public:
        Vertex(const Name &_name): colour(WHITE), name(_name) {}
        Vertex(): colour(WHITE) {};
        Name get_name() const { return name; }
        EColour colour;
        Vertex* parent;

        In_Edge_Iterator in_edge_begin() { return In_Edge_Iterator(in_edges.begin()); }
        In_Edge_Iterator in_edge_end() { return In_Edge_Iterator(in_edges.end()); }

        Out_Edge_Iterator out_edge_begin() { return Out_Edge_Iterator(out_edges.begin()); }
        Out_Edge_Iterator out_edge_end() { return Out_Edge_Iterator(out_edges.end()); }
      private:
        Name name;
        map<Vertex*, Edge*> out_edges;
        map<Vertex*, Edge*> in_edges;
    };

    explicit BiGraph(bool o):edges_count(0), orient(o) {}
    BiGraph():edges_count(0), orient(true){}
    ~BiGraph(){ clear(); }
    void clear();

    Vertex_Iterator begin() { return Vertex_Iterator(vertices_map.begin()); }
    Vertex_Iterator end() { return Vertex_Iterator(vertices_map.end()); }

    pair<bool, Vertex*> add_vertex(const Name &v);
    Edge* add_edge(const Name &start,const Name & end, double weight);

    Edge* add_edge(Vertex* start, Vertex* end, double weight) {
          add_edge(start->get_name(), end->get_name(), weight);
    }

    Edge* add_double_edge(const Name &start,const Name & end, double weight);
    bool delete_edge(const Name& start,const Name& end);

    Vertex* get_vertex(const Name& n) { return vertices_map[n]; }

    Edge* get_edge(const Name& n1, const Name& n2) {
        return vertices_map[n1]->out_edges[vertices_map[n2]];
    }

    Edge* get_edge(Vertex* n1, Vertex* n2) {
        return get_edge(n1->get_name(), n2->get_name());
    }

    void BFS(Vertex* srcIdx) const ;

    bool getPath(const Name& start, const Name& end, vector<Vertex*>& path);

    void Ford_Fulkerson(const Name& start, const Name& end);

  private:
    map<Name,Vertex*> vertices_map;
    size_t edges_count;
    bool orient;

    Vertex* find_or_create_vertex(const Name &v);
};

template <typename T>
typename BiGraph<T>::Edge* BiGraph<T>::add_edge(const T &start,const T & end, double weight){
    if (start==end) {
        add_vertex(start);
        return 0;
    }

    Vertex* start_vertex = find_or_create_vertex(start);
    Vertex* end_vertex = find_or_create_vertex(end);

    map_VE_It existing_edge=start_vertex->out_edges.find(end_vertex);

    if ( existing_edge!=start_vertex->out_edges.end()){ return existing_edge->second; }
    Edge* new_edge = new Edge(start_vertex, end_vertex, weight);
    start_vertex->out_edges.insert(make_pair(end_vertex, new_edge));
    end_vertex->in_edges.insert(make_pair(start_vertex, new_edge));

    ++edges_count;

    if (!orient) { add_edge(end, start, weight); }
    return new_edge;
}

template <typename T>
bool BiGraph<T>::delete_edge(const T& start,const T& end){
    if (vertices_map.find(start)==vertices_map.end()) { return false; }
    if (vertices_map.find(end)==vertices_map.end()) { return false; }

    Vertex* start_vertex = vertices_map[start];
    Vertex* end_vertex = vertices_map[end];
    if ( start_vertex->out_edges.find(end_vertex)==start_vertex->out_edges.end()) { return false; }
    start_vertex->out_edges.erase(end_vertex);
    delete end_vertex->in_edges[start_vertex];
    end_vertex->in_edges.erase(start_vertex);

    --edges_count;
    return true;
}

template <typename T>
pair<bool, typename BiGraph<T>::Vertex*> BiGraph<T>::add_vertex(const T &v){
    if ( vertices_map.find(v)!=vertices_map.end()) { return make_pair(false, vertices_map[v]); }
    Vertex* y  = new Vertex(v);
    vertices_map.insert(make_pair(v, y));

    return make_pair(true, y);
}

template <typename T>
void BiGraph<T>::clear() {
    for (map_NV_It i=vertices_map.begin(); i!=vertices_map.end();++i){
        for (Out_Edge_Iterator y = i->second->out_edge_begin(); y!=i->second->out_edge_end(); ++y) { delete &(*y); }
        delete i->second;
    }
    vertices_map.clear();
}

template <typename T>
typename BiGraph<T>::Vertex* BiGraph<T>::find_or_create_vertex(const T &v){
    if (vertices_map.find(v)==vertices_map.end()) {
        Vertex* new_vertex = new Vertex(v);
        vertices_map.insert(make_pair(v, new_vertex));
        return new_vertex;
    }
    return vertices_map[v];
}

template <typename T>
typename BiGraph<T>::Edge* BiGraph<T>::add_double_edge(const T &start,const T & end, double weight){
    add_edge(end, start, 0);
    return add_edge(start, end, weight);
}

template <typename T>
void BiGraph<T>::BFS(Vertex* start) const {
    std::deque<Vertex*> q;
    q.push_back(start);
    start->colour=GRAY;
    while(!q.empty()){
        Vertex* current = q.front();
        q.pop_front();
        current->colour=BLACK;
        for(Out_Edge_Iterator i = current->out_edge_begin(); i != current->out_edge_end(); ++i) {
            if (i->c - i->f > 0) {
                Vertex* sec = (i->get_vertices()).second;
                if(sec->colour == WHITE) {
                    sec->colour = GRAY;
                    sec->parent = current;
                    q.push_back(sec);
                    sec->colour = BLACK;
                }
            }
        }
    }
}

template <typename T>
bool BiGraph<T>::getPath(const T& start, const T& end, vector< typename BiGraph<T>::Vertex* >& path) {
    Vertex* strt = get_vertex(start);
    Vertex* nd = get_vertex(end);

    for (Vertex_Iterator i = begin(); i != this->end(); ++i) {
        i->parent = NULL;
        i->colour = WHITE;
    }

    BFS(strt);
    if (!nd->parent) return false;

    Vertex* cur = nd;
    while (cur != strt) {
        path.push_back(cur);
        cur = cur->parent;
    }
    path.push_back(strt);
    return true;
}

template <typename T>
void BiGraph<T>::Ford_Fulkerson(const T& start, const T& end) {
    for (Vertex_Iterator i = begin(); i != this->end(); ++i) {
        for (Out_Edge_Iterator y = i->out_edge_begin(); y != i->out_edge_end(); ++y) { y->f = 0; }
    }

    vector<Vertex*> path;
    bool fl = getPath(start, end, path);
    while (fl) {
        double c_path = std::numeric_limits<double>::max();
        for (int i = path.size()-1; i >= 1; --i) {
            Edge* rebro = get_edge(path[i], path[i-1]);
            if (rebro->c - rebro->f < c_path) {
                c_path = rebro->c - rebro->f;
            }
        }

        for (int i = path.size()-1; i >= 1; --i) {
            Edge* rebro = get_edge(path[i], path[i-1]);
            rebro->f = rebro->f + c_path;
            Edge* back_rebro = get_edge(path[i-1], path[i]);
            back_rebro->f = (-1) * rebro->f;
        }
        path.clear();
        fl = getPath(start, end, path);
    }

}
